#include <stdio.h>

#define N 10
/**
 * File: Exercise1006.c
 * -------------------------------------------------------
 * 1.6 Give the contents of the `id` array after each `union` operation for the weighted quick-union algorithm
 * running on the examples corresponding to Figure 1.7 and Figure 1.8.
 * -------------------------------------------------------
 * 输入
 * 3 4 4 9 8 0 2 3 5 6 2 9 5 9 7 3 4 8 5 6 0 2 6 1
 * 0 1 2 3 4 5 6 7 8 9 1 2 5 6 1 5 1 8
 * -------------------------------------------------------
 * 出处：[WeightedQuickUnion.c](https://gitcode.com/haoly1989/books/blob/main/AlgorithmsInC/examples/chapter1/WeightedQuickUnion.c)
 */
int main(int argc, char **argv){
    int i, p, q, j;
    int id[N];
    int sz[N];

    //初始化id数组值为索引值
    for (i = 0; i < N; i++) {
        id[i] = i;
        sz[i] = 1;
    }

    // 依次处理输入对：查找+合并
    while (scanf("%d %d\n", &p, &q) == 2) {
        //如果set(p)和set(q)相等，则表示p和q相连
        //寻找p所在树的根节点，用i来记录
        for (i = p; i != id[i]; i = id[i]) {
            ;
        }
        //寻找q所在树的根节点，用j来记录
        for (j = q; j != id[j]; j = id[j]) {
            ;
        }
        if (i == j) {
            //如果i==j(p所在树的根节点等于q所在树的根节点)，即set(p)和set(q)相等，则表示p和q相连
            continue;
        }
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        }else {
            id[j] = i;
            sz[i] += sz[j];
        }
        // printf("%d %d\n", p, q);
        for (int k = 0; k < N; k++) {
            printf("%d ", id[k]);
        }
        printf("\n");
    }
    return 0;
}

//每次union后，id数组的内容
//图1.7的输入：3 4 4 9 8 0 2 3 5 6 2 9 5 9 7 3 4 8 5 6 0 2 6 1
// 0 1 2 3 3 5 6 7 8 9 
// 0 1 2 3 3 5 6 7 8 3 
// 8 1 2 3 3 5 6 7 8 3 
// 8 1 3 3 3 5 6 7 8 3 
// 8 1 3 3 3 5 5 7 8 3 
// 8 1 3 3 3 3 5 7 8 3 
// 8 1 3 3 3 3 5 3 8 3 
// 8 1 3 3 3 3 5 3 3 3 

//图1.8的输入：0 1 2 3 4 5 6 7 8 9 1 2 5 6 1 5 1 8
// 0 0 2 3 4 5 6 7 8 9 
// 0 0 2 2 4 5 6 7 8 9 
// 0 0 2 2 4 4 6 7 8 9 
// 0 0 2 2 4 4 6 6 8 9 
// 0 0 2 2 4 4 6 6 8 8 
// 0 0 0 2 4 4 6 6 8 8 
// 0 0 0 2 4 4 4 6 8 8 
// 0 0 0 2 0 4 4 6 8 8 